package com.example.common_network;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Author: liaohailong
 * Date: 2022/2/16
 * Time: 11:05
 * Description:
 **/
public class Daily {

    // 6. Z 字形变换
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;

        ArrayList<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < Math.min(numRows, s.length()); i++) {
            rows.add(new StringBuilder());
        }

        int y = 0;
        boolean down = false;
        for (int i = 0; i < s.length(); i++) {
            rows.get(y).append(s.charAt(i));
            if (y == 0 || y == numRows - 1) down = !down;
            y += down ? 1 : -1;
        }

        StringBuilder sb = new StringBuilder();
        for (StringBuilder row : rows) {
            sb.append(row.toString());
        }
        return sb.toString();
    }


    // 4. 寻找两个正序数组的中位数 时间：O(n) 空间：O(n)
//    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
//        int[] arr = new int[nums1.length + nums2.length];
//        int k = 0;
//        int i = 0;
//        int j = 0;
//        while (k < arr.length) {
//            if (i < nums1.length && j < nums2.length) {
//                if (nums1[i] < nums2[j]) {
//                    arr[k++] = nums1[i++];
//                } else arr[k++] = nums2[j++];
//            } else if (j < nums2.length) {
//                arr[k++] = nums2[j++];
//            } else {
//                arr[k++] = nums1[i++];
//            }
//        }
//
//        return arr.length % 2 == 0 ? (arr[arr.length / 2 - 1] + arr[arr.length / 2]) / 2f : arr[arr.length / 2];
//    }


    // 4. 寻找两个正序数组的中位数 时间：O(m+n) 空间：O(1)
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 转换为求两个有序数组中，第k小的值
        int length = nums1.length + nums2.length;
        if (length % 2 == 0) {
            int left = length / 2;
            int right = length / 2 + 1;
            return (getMin(nums1, nums2, left) + getMin(nums1, nums2, right)) / 2f;
        } else {
            int mid = length / 2 + 1;
            return getMin(nums1, nums2, mid);
        }
    }

    // 获取两个正序数组中，第k小的值
    public int getMin(int[] arr1, int[] arr2, int k) {
        if (arr1.length <= 0) return arr2[k - 1];
        if (arr2.length <= 0) return arr1[k - 1];

        // 先找第k/2个值，arr1[k/2 -1] < arr2[k/2 -1] 则可以排除arr1[k/2]之前的所有值
        // (k/2-1) + (k/2-1) <= k-2 这样删除，最少会保留第k-2个最小值
        // k = k - min(k/2,{arr1可比范围，arr2可比范围})
        // k == 1时，min(arr[i],arr[j]) = 第k小的值
        int i = 0;
        int j = 0;
        while (true) {
            if (k == 1) return Math.min(arr1[i], arr2[j]);

            int offset = k / 2;
            int pos = offset - 1;

            // arr1边界问题：缩小offset
            if (i + pos > arr1.length - 1) {
                offset = arr1.length - i;
                pos = offset - 1;
            }

            // arr2边界问题：缩小offset
            if (j + pos > arr2.length - 1) {
                offset = arr2.length - j;
                pos = offset - 1;
            }

            if (arr1[i + pos] < arr2[j + pos]) {
                i = i + pos + 1;
            } else j = j + pos + 1;

            k -= offset;

            if (i >= arr1.length) {
                return arr2[j + k - 1];
            }
            if (j >= arr2.length) {
                return arr1[i + k - 1];
            }
        }
    }


//    // 9. 回文数 转字符串方式
//    public boolean isPalindrome(int x) {
//        String str = String.valueOf(x);
//        if (str.length() % 2 == 0) {
//            int left = str.length() / 2 - 1;
//            int right = str.length() / 2;
//            return isPalindrome(str, left, right);
//        } else {
//            int mid = str.length() / 2;
//            return isPalindrome(str, mid, mid);
//        }
//    }
//
//    private boolean isPalindrome(String s, int i, int j) {
//        while (i >= 0 && j < s.length()) {
//            if (s.charAt(i) == s.charAt(j)) {
//                i--;
//                j++;
//            } else return false;
//        }
//        return true;
//    }

    // 9. 回文数 不转字符串
    public boolean isPalindrome(int x) {
        // 负数和各位为0的数字都不是回文数（0是回文数）
        if (x < 0 || (x != 0 && x % 10 == 0)) return false;

        // 奇数
        // 12321 0
        // 1232  1
        // 123   12
        // 12    123

        // 偶数
        // 123321 0
        // 12332  1
        // 1233   12
        // 123    123

        int reserve = 0;
        while (x > reserve) {
            reserve = reserve * 10 + x % 10;
            x /= 10; // 时间复杂：log10 N
        }

        return x == reserve || x == reserve / 10;
    }


    // 11. 盛最多水的容器 暴力法 O(n2)
//    public int maxArea(int[] height) {
//        int[] lines = new int[height.length];
//        int max = 0;
//        for (int i = 0; i < lines.length; i++) {
//            for (int j = i + 1; j < lines.length; j++) {
//                int width = j - i;
//                int size = width * Math.min(height[i], height[j]);
//                lines[i] = Math.max(lines[i], size);
//            }
//            if (lines[i] > max) max = lines[i];
//        }
//
//        return max;
//    }

    // 11. 盛最多水的容器 双指针+数学推导
    public int maxArea(int[] height) {
        int max = 0;
        int i = 0;
        int j = height.length - 1;
        while (j > i) {
            int min = Math.min(height[i], height[j]);
            max = Math.max(max, min * (j - i));
            // 哪边小，移动哪边
            if (height[i] < height[j])
                i++;
            else
                j--;
        }

        return max;
    }


    // 12. 整数转罗马数字 O(n2)
//    public String intToRoman(int num) {
////        字符          数值
////        I             1
////        V             5
////        X             10
////        L             50
////        C             100
////        D             500
////        M             1000
//
//        // 个位、十位、百位、千位
//        Map<Integer, char[]> map = new HashMap<>();
//        map.put(1, new char[]{'I', 'V'});
//        map.put(2, new char[]{'X', 'L'});
//        map.put(3, new char[]{'C', 'D'});
//        map.put(4, new char[]{'M', 'M'});
//
//        LinkedList<String> queue = new LinkedList<>();
//
//        LinkedList<Integer> list = new LinkedList<>();
//        while (num != 0) {
//            list.addFirst(num % 10);
//            num /= 10;
//        }
//
//        StringBuilder res = new StringBuilder();
//        for (int i = 0; i < list.size(); i++) {
//            int key = list.size() - i;
//            char[] roman = map.get(key);
//            StringBuilder sb = new StringBuilder();
//            int val = list.get(i);
//            if (val < 4) {
//                for (int j = 0; j < val; j++) {
//                    sb.append(roman[0]);
//                }
//            } else if (val == 4) {
//                sb.append(roman[0]).append(roman[1]);
//            } else if (val == 5) {
//                sb.append(roman[1]);
//            } else if (val < 9) {
//                sb.append(roman[1]);
//                for (int j = 0; j < val - 5; j++) {
//                    sb.append(roman[0]);
//                }
//            } else if (val == 9) {
//                char[] roman1 = map.get(key + 1);
//                sb.append(roman[0]).append(roman1[0]);
//            }
//
//            res.append(sb.toString());
//        }
//
//        return res.toString();
//
//    }


    // 12. 整数转罗马数字 O(1)
    public String intToRoman(int num) {
//        字符          数值
//        I             1
//        V             5
//        X             10
//        L             50
//        C             100
//        D             500
//        M             1000

        // 从左边开始，用最大的数字代替，得出减法法则
        // 数学问题：
        // 140 = ?
        // L L XL = 50 50 40
        // C X X X X = 100 10 10 10 10
        // C XL = 100 40
        // XC L = 90 50
        // XL XL XL X X = 40 40 40 10 10 = 140
        // C X X V V V V = 100 10 10 5 5 5 5 = 140
        int[] value = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbol = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < symbol.length; i++) {
            String s = symbol[i];
            int v = value[i];
            while (num >= v) {
                num -= v;
                sb.append(s);
            }
            if (num <= 0) break;
        }

        return sb.toString();
    }


    // 16. 最接近的三数之和
    public int threeSumClosest(int[] nums, int target) {
        // 排序 + 双指针 + 比较缩小范围
        // 取出3个数 a b c 之和离target最近
        // b c 与 target - a 的距离最近
        // abs(target - (b+c)) < abs(target - a)
        Arrays.sort(nums);

        int best = 3001;
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 去除重复比较
            int a = nums[i];
            int pb = i + 1;
            int pc = nums.length - 1;
            while (pc > pb) {
                int total = a + nums[pc] + nums[pb];
                if (total == target) return total; // 找到了

                // 找出距离更小的三数之和
                if (Math.abs(best - target) > Math.abs(total - target)) {
                    best = total;
                }

                // abc值偏大，此时需要将pc指针向左偏移，找出更小的值
                if (total > target) {
                    pc--;
                    while (pc > pb && nums[pc] == nums[pc + 1]) pc--;
                }
                // abc值偏大，此时需要将pb指针向右偏移，找出更大的值
                else {
                    pb++;
                    while (pc > pb && nums[pb] == nums[pb - 1]) pb++;
                }
            }
        }

        return best;
    }


    // 15. 三数之和c 排序 + 双指针
    public List<List<Integer>> threeSum(int[] nums) {
        // 升序方便去重复
        Arrays.sort(nums);
        // 找出3个数，a+b+c == 0
        // 转换为 b+c = -a
        List<List<Integer>> list = new LinkedList<>();

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) continue; // 大于0，肯定后面没有解了
            if (i > 0 && nums[i - 1] == nums[i]) continue; // 相同的数字找过了
            int a = nums[i];

            int pb = i + 1;
            int pc = nums.length - 1;
            while (pc > pb) {
                int total = a + nums[pb] + nums[pc];

                if (total == 0) {
                    List<Integer> l = new LinkedList<>();
                    l.add(a);
                    l.add(nums[pb]);
                    l.add(nums[pc]);
                    list.add(l);
                }

                // total偏大，右指针左移
                if (total > 0) {
                    pc--;
                    while (pc > pb && nums[pc] == nums[pc + 1]) pc--;
                }
                // total偏小，左指针右移
                else {
                    pb++;
                    while (pc > pb && nums[pb] == nums[pb - 1]) pb++;
                }
            }
        }

        return list;
    }

    // 18. 四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // 排序，去重复查找
        Arrays.sort(nums);

        List<List<Integer>> list = new LinkedList<>();
        // a+b+c+d=target
        // a = target-b-c-d
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;// 上个已找出
            if (i >= nums.length - 3) continue; // 4个数字至少

            int a = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;// 上个已找出
                int b = nums[j];

                int pc = j + 1;
                int pd = nums.length - 1;

                while (pc < pd) {
                    if (a + b + nums[pc] + nums[pd] == target) {
                        List<Integer> l = new LinkedList<>();
                        l.add(a);
                        l.add(b);
                        l.add(nums[pc]);
                        l.add(nums[pd]);
                        list.add(l);
                    }

                    if (a + b + nums[pc] + nums[pd] > target) {
                        pd--;
                        while (pc < pd && nums[pd] == nums[pd + 1]) pd--;
                    } else {
                        pc++;
                        while (pc < pd && nums[pc] == nums[pc - 1]) pc++;
                    }
                }
            }
        }

        return list;
    }


    // 31. 下一个排列
    public void nextPermutation(int[] nums) {
        if (nums.length < 2) return;

        // 从右往左，找出第一个非降序值
        int i = nums.length - 1;
        int j = -1;
        while (i > 0) {
            if (nums[i - 1] < nums[i]) {
                j = i - 1;
                break;
            } else i--;
        }

        // 从降序列表中，找出大于nums[j]的最小值
        i = nums.length - 1;
        while (j != -1 && i > j) {
            if (nums[i] > nums[j]) {
                break;
            }
            i--;
        }

        // swap
        if (j != -1) {
            nums[i] = nums[i] ^ nums[j];
            nums[j] = nums[i] ^ nums[j];
            nums[i] = nums[i] ^ nums[j];
        }

        // 降序数组变升序数组，最快办法是反转
        // reserve
        int left = j + 1;
        int right = nums.length - 1;
        while (left < right) {
            int temp = nums[right];
            nums[right] = nums[left];
            nums[left] = temp;
            left++;
            right--;
        }
    }

    // 39. 组合总和 全排序 + 去重复 i:0..N [j:i..N [k: j..N]] 摘葡萄
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new LinkedList<>();
        LinkedList<Integer> path = new LinkedList<>();
        int[] curr = new int[1];
        // dfs
        _combinationSum(candidates, 0, path, curr, target, list);
        return list;
    }

    private void _combinationSum(int[] candidates, int from, LinkedList<Integer> path,
                                 int[] curr, int target, List<List<Integer>> list) {
        if (curr[0] == target) {
            List<Integer> l = new LinkedList<>(path);
            list.add(l);
            return;
        }
        if (curr[0] > target) return;
        for (int i = from; i < candidates.length; i++) {
            path.addLast(candidates[i]);
            curr[0] += candidates[i];
            _combinationSum(candidates, i, path, curr, target, list);
            curr[0] -= candidates[i];
            path.pollLast();
        }
    }

    // 40. 组合总和 II 每个元素只能使用一次 排序candidates + dfs + 起点偏移剪枝
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        LinkedList<List<Integer>> list = new LinkedList<>();
        LinkedList<Integer> path = new LinkedList<>();
        int[] curr = new int[1];
        _combinationSum2(candidates, target, 0, path, curr, list);
        return list;
    }

    private void _combinationSum2(int[] candidates, int target, int from,
                                  LinkedList<Integer> path, int[] curr,
                                  List<List<Integer>> list) {
        if (curr[0] == target) {
            List<Integer> l = new LinkedList<>(path);
            list.add(l);
            return;
        }
        if (curr[0] > target) return;
        for (int i = from; i < candidates.length; i++) {
            if (i > from && candidates[i] == candidates[i - 1]) continue; // 从左边开始，去重复
            path.addLast(candidates[i]);
            curr[0] += candidates[i];
            _combinationSum2(candidates, target, i + 1, path, curr, list);
            curr[0] -= candidates[i];
            path.pollLast();
        }
    }


    // 43. 字符串相乘
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        String total = "";
        String times = "";
        for (int i = 0; i < num1.length(); i++) {
            int p = num1.length() - 1 - i;
            char val = num1.charAt(p);
            int value = Character.digit(val, 10);
            String curr = _multiply(num2, value);
            curr += times;
            times += "0";
            // add two string number
            total = _addStrings(total, curr);
        }

        return total;
    }

    private String _multiply(String num, int val) {
        StringBuilder sb = new StringBuilder();
        int extra = 0;
        for (int i = 0; i < num.length(); i++) {
            int p = num.length() - 1 - i;
            char c = num.charAt(p);
            int val0 = Character.digit(c, 10);
            int res = val0 * val;
            if (extra > 0) {
                res += extra;
                extra = 0;
            }
            int one = res % 10;
            int ten = res / 10;
            sb.insert(0, one);
            if (ten > 0) extra = ten;
        }
        if (extra > 0) sb.insert(0, extra);
        return sb.toString();
    }

    private String _addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int extra = 0;
        while (i >= 0 || j >= 0 || extra > 0) {
            int total = 0;
            if (i >= 0) {
                total += Character.digit(num1.charAt(i), 10);
                i--;
            }
            if (j >= 0) {
                total += Character.digit(num2.charAt(j), 10);
                j--;
            }

            if (extra != 0) {
                total += extra;
                extra = 0;
            }

            if (total >= 10) {
                extra = total / 10;
                total %= 10;
            }
            sb.insert(0, total);
        }
        return sb.toString();
    }


    // 47. 全排列 II
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);

        List<List<Integer>> list = new LinkedList<>();
        LinkedList<Integer> path = new LinkedList<>();
        boolean[] visitor = new boolean[nums.length];
        // dfs
        _permuteUnique(nums, visitor, path, list);
        return list;
    }

    private void _permuteUnique(int[] nums,
                                boolean[] visitor,
                                LinkedList<Integer> path,
                                List<List<Integer>> list) {
        if (path.size() >= nums.length) {
            list.add(new LinkedList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 祖辈找过的不着了
            if (visitor[i]) continue;
            //                                          如果是false表示相同的元素是兄弟节点，兄弟在左，左边的已经找过了
            //                                          如果是true表示为父子节点，父子节点是第一次添加，需画图理解
            //                                          👇
            if (i > 0 && nums[i] == nums[i - 1] && !visitor[i - 1]) continue;
            path.addLast(nums[i]);
            visitor[i] = true;
            _permuteUnique(nums, visitor, path, list);
            path.pollLast();
            visitor[i] = false;
        }
    }

    // 54. 螺旋矩阵
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new LinkedList<>();
        // 1，确定圈数
        // 2，确认路线：上右下左
        // 3，确认边界值
        int y = matrix.length;
        int x = matrix[0].length;
        int z = (Math.min(y, x) + 1) / 2; // 圈数

        for (int i = 0; i < z; i++) {
            // 起点
            // 左上
            int y0 = i;
            int x0 = i;
            // 右上
            int y1 = i;
            int x1 = x - 1 - i;
            // 右下
            int y2 = y - 1 - i;
            int x2 = x - 1 - i;
            // 左下 与左上不接触
            int y3 = y - 1 - i;
            int x3 = i;

            // 特殊情况
            if (i == z - 1) {
                // 最后一个圈，可能组成不了一个回型
                if (x0 == x1) {
                    // 点 or 一条竖线
                    for (int j = y0; j <= y2; j++) {
                        result.add(matrix[j][x0]);
                    }
                    return result;
                } else if (y1 == y2) {
                    // 一条横线
                    for (int j = x0; j <= x1; j++) {
                        result.add(matrix[y0][j]);
                    }
                    return result;
                }
            }

            // 遍历 左上-右上 左闭右开
            for (int j = x0; j < x1; j++) {
                result.add(matrix[y0][j]);
            }

            // 遍历 右上-右下 上闭下开
            for (int j = y1; j < y2; j++) {
                result.add(matrix[j][x1]);
            }

            // 遍历 右下-左下 右闭左开
            for (int j = x2; j > x3; j--) {
                result.add(matrix[y3][j]);
            }

            // 遍历 左下-左上 下闭上开
            for (int j = y3; j > y0; j--) {
                result.add(matrix[j][x3]);
            }
        }

        return result;
    }


    // 57. 插入区间
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length < 1) return new int[][]{newInterval};

        LinkedList<int[]> list = new LinkedList<>(Arrays.asList(intervals));

        int i;
        // 找到插入位置 二分法
        int low = 0;
        int high = intervals.length - 1;
        while (true) {
            // 找到
            if (high - low <= 1) {
                i = high + 1;
                for (int k = low; k <= high; k++) {
                    if (newInterval[0] <= intervals[k][1]) {
                        i = k;
                        break;
                    }
                }
                break;
            }

            int mid = low + ((high - low) >> 1);
            if (newInterval[0] == intervals[mid][0]) {
                // 找到
                i = mid;
                break;
            } else if (newInterval[0] > intervals[mid][0]) {
                // 在右边
                low = mid + 1;
            } else if (newInterval[0] < intervals[mid][0]) {
                // 在左边
                high = mid - 1;
            }
        }

        // 插入区间
        list.add(i, newInterval);

        int from = Math.max(0, i - 1);
        // 从i个开始，向后合并区间
        while (from < list.size() - 1) {
            int[] first = list.get(from);
            int[] second = list.get(from + 1);

            // 需要合并
            if (second[0] <= first[1]) {
                int[] combined = new int[2];
                combined[0] = Math.min(first[0], second[0]);
                combined[1] = Math.max(first[1], second[1]);
                list.remove(first);
                list.remove(second);
                list.add(from, combined);
            } else {
                // 不需要合并
                from++;
            }
        }

        int[][] result = new int[list.size()][2];
        int p = 0;
        while (!list.isEmpty()) {
            int[] ints = list.pollFirst();
            result[p++] = ints;
        }
        return result;
    }


    // 58. 最后一个单词的长度
    public int lengthOfLastWord(String s) {
        int N = s.length();

        int last = -1;
        int length = 0;
        for (int i = 0; i < N; i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                if (last != -1) {
                    length = i - last;
                }
                last = -1;
            } else {
                if (last == -1) {
                    // 新的起点
                    last = i;
                    length = 1;
                } else {
                    length = i - last + 1;
                }
            }
        }

        return length;
    }

    // 59. 螺旋矩阵 II
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];

        // 1，确定圈数
        // 2，确认路线：上右下左
        // 3，确认边界值
        int y = matrix.length;
        int x = matrix[0].length;
        int z = (Math.min(y, x) + 1) / 2; // 圈数

        int step = 1;
        for (int i = 0; i < z; i++) {
            // 起点
            // 左上
            int y0 = i;
            int x0 = i;
            // 右上
            int y1 = i;
            int x1 = x - 1 - i;
            // 右下
            int y2 = y - 1 - i;
            int x2 = x - 1 - i;
            // 左下 与左上不接触
            int y3 = y - 1 - i;
            int x3 = i;

            // 特殊情况
            if (i == z - 1) {
                // 最后一个圈，可能组成不了一个回型
                if (x0 == x1) {
                    // 点 or 一条竖线
                    for (int j = y0; j <= y2; j++) {
                        matrix[j][x0] = step++;
                    }
                    return matrix;
                } else if (y1 == y2) {
                    // 一条横线
                    for (int j = x0; j <= x1; j++) {
                        matrix[y0][j] = step++;
                    }
                    return matrix;
                }
            }

            // 遍历 左上-右上 左闭右开
            for (int j = x0; j < x1; j++) {
                matrix[y0][j] = step++;
            }

            // 遍历 右上-右下 上闭下开
            for (int j = y1; j < y2; j++) {
                matrix[j][x1] = step++;
            }

            // 遍历 右下-左下 右闭左开
            for (int j = x2; j > x3; j--) {
                matrix[y3][j] = step++;
            }

            // 遍历 左下-左上 下闭上开
            for (int j = y3; j > y0; j--) {
                matrix[j][x3] = step++;
            }
        }

        return matrix;
    }

    // 63. 不同路径 II 网格中的障碍物和空位置分别用 1 和 0 来表示
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int column = obstacleGrid[0].length;
        int[] visitor = new int[column];

        visitor[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (obstacleGrid[i][j] == 1) {
                    visitor[j] = 0;
                    continue;
                }
                if (j > 0 && obstacleGrid[i][j - 1] == 0) {
                    visitor[j] += visitor[j - 1];
                }
            }
        }
        return visitor[column - 1];
    }

    // 64. 最小路径和
    public int minPathSum(int[][] grid) {
        int m = grid.length; // 行
        int n = grid[0].length; // 列

        int[] dp = new int[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    if (j == 0)
                        dp[0] = grid[0][0];
                    else dp[j] = dp[j - 1] + grid[i][j];
                } else {
                    if (j == 0) {
                        dp[0] += grid[i][j];
                    } else {
                        int min = Math.min(dp[j - 1], dp[j]);
                        dp[j] = min + grid[i][j];
                    }
                }
            }
        }

        return dp[n - 1];
    }

    // 67. 二进制求和
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int N = Math.max(a.length(), b.length());
        int extra = 0;
        for (int i = 0; i < N; i++) {
            int pa = a.length() - 1 - i;
            int pb = b.length() - 1 - i;
            if (pa >= 0 && pb >= 0) {
                int ia = Character.digit(a.charAt(pa), 10);
                int ib = Character.digit(b.charAt(pb), 10);
                int total = ia + ib;
                if (extra > 0) {
                    total += extra;
                    extra = 0;
                }
                if (total >= 2) {
                    extra = 1;
                    total -= 2;
                }
                sb.insert(0, total);
            } else {
                int total = pb >= 0 ?
                        Character.digit(b.charAt(pb), 10)
                        : Character.digit(a.charAt(pa), 10);
                if (extra > 0) {
                    total += extra;
                    extra = 0;
                }
                if (total >= 2) {
                    extra = 1;
                    total -= 2;
                }
                sb.insert(0, total);
            }
        }

        if (extra > 0) sb.insert(0, extra);

        return sb.toString();
    }


    // 71. 简化路径
    public String simplifyPath(String path) {
        LinkedList<String> queue = new LinkedList<>();

        int last = -1;
        for (int i = 1; i < path.length(); i++) {
            char c = path.charAt(i);
            if (c != '/') {
                if (last == -1) last = i;
            } else {
                if (last != -1) {
                    String part = path.substring(last, i);
                    if (part.equals(".")) {
                        // do nothing...
                    } else if (part.equals("..")) {
                        if (!queue.isEmpty())
                            queue.removeLast();
                    } else
                        queue.addLast(part);
                    last = -1;
                }
            }
        }

        // 取出最后一个
        if (last != -1) {
            String part = path.substring(last);
            if (part.equals(".")) {
                // do nothing...
            } else if (part.equals("..")) {
                if (!queue.isEmpty())
                    queue.removeLast();
            } else
                queue.addLast(part);
        }

        StringBuilder sb = new StringBuilder();
        if (queue.isEmpty())
            sb.append("/");
        else
            for (String s : queue) {
                sb.append("/").append(s);
            }

        return sb.toString();
    }

    // 74. 搜索二维矩阵
    // 每一行的数按升序排序
    // 每一行的第一个数大于前一行的最后一个数
    public boolean searchMatrix(int[][] matrix, int target) {
        int N = matrix.length;
        // 1，确定行，二分法
        int low = 0;
        int high = N;
        int index = 0;
        while (true) {
            int mid = low + ((high - low) >> 1);

            if (matrix[mid][0] <= target) {
                if (mid + 1 >= N) {
                    // 已经是最后一行
                    index = mid;
                    break;
                } else {
                    if (matrix[mid + 1][0] > target) {
                        index = mid;
                        break;
                    } else {
                        low = mid + 1;
                    }
                }
            } else if (matrix[mid][0] > target) {
                high = mid - 1;
            }

            if (low >= high) {
                index = low;
                break;
            }
        }

        // 2，查找列中是否存在
        int[] arr = matrix[index];

        low = 0;
        high = arr.length;
        while (true) {
            int mid = low + ((high - low) >> 1);
            if (arr[mid] == target) return true;

            if (arr[mid] > target) {
                high = mid - 1;
            } else if (arr[mid] < target) {
                low = mid + 1;
            }

            if (low >= high) {
                low = Math.min(arr.length - 1, low);
                high = Math.max(0, high);
                high = Math.min(arr.length - 1, high);
                return arr[low] == target || arr[high] == target;
            }
        }
    }

    // 77. 组合
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new LinkedList<>();
        LinkedList<Integer> path = new LinkedList<>();
        // dfs
        _combine(1, n, k, path, result);

        return result;
    }

    private void _combine(int from, int to, int k,
                          LinkedList<Integer> path,
                          List<List<Integer>> result) {
        // 数量不够，无法组合
        if (path.size() + (to - from + 1) < k) return;
        // 组合完毕
        if (path.size() >= k) {
            result.add(new LinkedList<>(path));
            return;
        }

        for (int i = from; i <= to; i++) {
            path.addLast(i);
            _combine(i + 1, to, k, path, result);
            path.removeLast();
        }
    }


}
